class kmeans_node:
    
      termination=False
      
      def __init__(self,initial, database,threshold):
      # initial is a list of the initial centriods of different criterions, 
      # database stores an array of criterions value, each column
      # corresponds to one criterions. Each row coressponds to one sample.
      # maximum and minimum is lists of max and mini values of criterions
          '''self.normaized_database=[]
          for sample in database:
              list=[]
              count=0
              for element in sample:
                  if(minimum[count]==maximum[count]):
                     list.append(1)
                  else:
                     list.append((element-minimum[count])/(maximum[count]-minimum[count]))
                  count=count+1
              self.normaized_database.append(list)'''
          self.normaized_database=database
          self.centroids=[]
          self.centroids.append(initial)
          self.centroids_counts=[]
          self.threshold=threshold
          '''self.minimum=minimum
          self.maximum=maximum'''
       

      def weighted_centroid_calculate(self,neighbor_data, num_of_neighbor):
          length=len(neighbor_data[0])
          sum_centroid_num=[[0]*len(neighbor_data[0][0][0])]*length
          sum_num=[0]*length
          centroid=[]
          list_add = lambda x,y : x+y

          for neighbor in neighbor_data:
              count=0
              for centroids in neighbor:
                  tmp=[centroids[1]*x for x in centroids[0]]
                  sum_centroid_num[count]=map(list_add,tmp,sum_centroid_num[count])
                  sum_num[count]=centroids[1]+sum_num[count]
                  count=count+1
          count=0
          for tmp in sum_centroid_num:
              if sum_num[count]==0:
                 tmp_list=[0]*len(tmp)
                 for neighbor in neighbor_data:
                     #print type(tmp_list)
                     #print type(neighbor[count])
                     tmp_list=map(list_add,tmp_list, neighbor[count][0])
                 centroid.append([x/num_of_neighbor for x in tmp_list])
              else:
                 centroid.append([x/sum_num[count] for x in tmp])
              count=count+1
          #print "inside weighted_centroid_calculate"
          #print self.terminate_check(self.threshold)
          if (len(self.centroids)<2 or self.termination==False):
              self.centroids.append(centroid)
          else: # if threshold is arrived, append the same centroids as the last one
              centroid=self.centroids.pop()
              self.centroids.append(centroid)
              self.centroids.append(centroid)

      def local_centroid_counts(self,centroids):
          counts=[0]*len(centroids)
          centr_counts=[]
          for sample in self.normaized_database:
              index,mini=self.find_centroid(sample,centroids)
              counts[index]=counts[index]+1
          count=0
          for centroid in centroids:
               centr_counts.append((centroid,counts[count]))
               count=count+1
          if (len(self.centroids_counts)<2 or self.termination==False):
              self.centroids_counts.append(centr_counts)
          else: # if threshold is arrived, append the same centroids as the last one
              centr_counts=self.centroids_counts.pop()
              self.centroids_counts.append(centr_counts)
              self.centroids_counts.append(centr_counts)
              

      def one_round_kmeans(self,centroids):
          #sample_cluster=[[]*len(centroids),[]*len(centroids)]
          sample_cluster=[]
          for centroid in centroids:
              sample_cluster.append([])
          for sample in self.normaized_database:
              index, mini=self.find_centroid(sample,centroids)
              sample_cluster[index].append(sample)
          new_centroids=[]
          #print len(sample_cluster[0])
          #print len(sample_cluster[1])
          
          list_add = lambda x,y : x+y
          count=0
          for cluster in sample_cluster:
              if len(cluster)==0:
                 new_centroids.append(centroids[count])
              else:
                 tmp=[0]*len(cluster[0])
                 for sample in cluster:
                     tmp=map(list_add,sample,tmp)
                 centroid=[]
                 for element in tmp:
                     element=element/len(cluster)
                     centroid.append(element)
                 new_centroids.append(centroid)
              count=count+1
          return new_centroids
          

      def find_centroid(self,sample,centroids):
          distance=[]
          for centroid in centroids:
              tmp=[]
              count=0
              for element in sample:
                  tmp.append((element-centroid[count])*(element-centroid[count]))
                  count=count+1
              distance.append(sum(tmp))
          mini=min(distance)
          return distance.index(mini),mini

      def terminate_check(self,threshold):
          length=len(self.centroids)
          current_centroids=self.centroids[length-1]
          #print current_centroids
          last_centroids=self.centroids[length-2]
          #print last_centroids
          difference=[]
          count=0
          distance_compute = lambda x,y : (x-y)*(x-y)
          for centroid in current_centroids:
              tmp=[]
              tmp=map(distance_compute,centroid,last_centroids[count])
              difference.append(sum(tmp))
              count=count+1
          maximum_difference=max(difference)
          if maximum_difference<=threshold:
             self.termination=True
             self.global_centroids=current_centroids
          else: 
             self.termination=False
             
              

      def final_cluster(self):
          cluster=[]
          cluster_distance=[]
          final=len(self.centroids_counts)-1
          final_centroids=[]
          sample_classified=[]
          for one in self.centroids[0]:
              sample_classified.append([])
          for centroid in self.centroids_counts[final]:
              final_centroids.append(centroid[0])
           
          for sample in self.normaized_database:
              index,distance=self.find_centroid(sample,final_centroids)
              sample_classified[index].append(sample)
              index=index+1
              cluster.append(index)
              cluster_distance.append(distance)
          return cluster,cluster_distance,sample_classified
      
      def database_change(self,database):
          self.normaized_database=database
          '''for sample in database:
              list=[]
              count=0
              for element in sample:
                  if(self.minimum[count]==self.maximum[count]):
                     list.append(1)
                  else:
                     list.append((element-self.minimum[count])/(self.maximum[count]-self.minimum[count]))
                  count=count+1
              self.normaized_database.append(list)'''
              
                  
          
